package top.lcm889.oj.按算法分类.双指针;


import java.util.List;

/**
 * @author Coder-lcm
 * @date 2021/2/5
 * 思路：使用双指针，一个指针每次移动一个节点，一个指针每次移动两个节点，如果存在环，那么这两个指针一定会相遇。
 */
public class T141_判断链表是否有环 {
    public static boolean hasCycle(ListNode head) {
        if (head == null){
            return false;
        }
        ListNode p1 = head, p2 = head.next;
        while (p1 != null && p2 != null && p2.next != null) {
            if (p1 == p2){
                return true;
            }
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return false;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(34);
        listNode.next = new ListNode(321);
        listNode.next.next = new ListNode(1314);
        System.out.println(hasCycle(listNode)); //false
        //特意设成环形链表
        listNode.next.next.next = listNode;
        System.out.println(hasCycle(listNode)); // true
        System.out.println(listNode.val);
        System.out.println(listNode.next.val);
        System.out.println(listNode.next.next.val);
        System.out.println(listNode.next.next.next.val);
    }
}

//链表结构类
class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val = x;
        next = null;
    }
}